/*
力扣 (LeetCode) https://leetcode-cn.com/leetbook/read/linked-list/fabl3/
下标从 0 开始！！！ 头节点 -> 节点0 -> 节点1
*/

#include <iostream>

// 定义双向链表结构体
struct DoublyListNode {
  int val;
  DoublyListNode *next, *prev;
  DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};

class MyLinkedList {
private:
  DoublyListNode *head; // 虚拟头节点，值为链表长度
  DoublyListNode *tail; // 虚拟尾节点，值为 -1（无特殊含义，仅作为标记）

public:
  MyLinkedList() {
    this->head = new DoublyListNode(0);
    this->tail = new DoublyListNode(-1);
    this->head->next = this->tail;
    this->tail->prev = this->head;
  }

  /* 获取链表中第 index 个节点的值。如果索引无效，则返回 -1。 */
  int get(int index) {
    if (index < 0 || index >= this->head->val) {
      return -1;
    }
    DoublyListNode *p;
    if (index / 2 < this->head->val) { // 二分查找
      p = this->head->next;
      while (index--) {
        p = p->next;
      }
    } else {
      p = this->tail;
      while (index--) {
        p = p->prev;
      }
    }

    return p->val;
  }

  /* 在链表的第一个元素之前添加一个值为 val
   * 的节点。插入后，新节点将成为链表的第一个节点。 */
  void addAtHead(int val) {
    DoublyListNode *p = new DoublyListNode(val);
    p->prev = this->head;
    p->next = this->head->next;
    this->head->next->prev = p;
    this->head->next = p;
    this->head->val++; // 长度加一
  }

  /* 在链表的第一个元素之前添加一个值为 val
   * 的节点。插入后，新节点将成为链表的第一个节点。 */
  void addAtTail(int val) {
    DoublyListNode *p = this->tail; // 尾节点
    DoublyListNode *q = new DoublyListNode(val);
    q->next = p;
    q->prev = p->prev;
    p->prev->next = q;
    p->prev = q;
    this->head->val++; // 长度加一
  }

  /* 在链表中的第 index 个节点之前添加值为 val 的节点。如果 index
   * 等于链表的长度，则该节点将附加到链表的末尾。如果 index
   * 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 */
  void addAtIndex(int index, int val) {
    if (index <= 0)
      addAtHead(val);
    else if (index == this->head->val)
      addAtTail(val);
    else if (index < this->head->val) {
      DoublyListNode *p = this->head;
      while (index--) { // 移动
        p = p->next;
      }
      DoublyListNode *q = new DoublyListNode(val);
      q->prev = p;
      q->next = p->next;

      p->next->prev = q;
      p->next = q;
      this->head->val++; // 长度加一
    }
  }

  /* 如果索引 index 有效，则删除链表中的第 index 个节点。 */
  void deleteAtIndex(int index) {
    if (index >= 0 && index < this->head->val) {
      DoublyListNode *p = this->head;
      while (index--) { // 移动到要删除的节点
        p = p->next;
      }
      DoublyListNode *q = p->next;
      if (p->next && p->next->next) { // 当删除的不是尾节点
        p->next->next->prev = p;
        p->next = p->next->next;
      } else {
        p->next = NULL;
      }

      delete q;
      this->head->val--; // 长度减一
    }
  }

  /* 按顺序显示链表全部元素 */
  void showList(char div = ' ') {
    DoublyListNode *p = this->head->next;
    while (p->next) { // 过滤尾结点
      std::cout << p->val << div;
      p = p->next;
    }
    std::cout << std::endl;
  }
};

int main() {
  MyLinkedList linkedList = *new MyLinkedList();
  linkedList.addAtHead(4);
  std::cout << linkedList.get(1) << std::endl;
  linkedList.addAtHead(1);
  linkedList.addAtHead(5);
  linkedList.showList();
  linkedList.deleteAtIndex(3);
  linkedList.showList();
  linkedList.addAtHead(7);
  linkedList.addAtHead(8);
  linkedList.showList();
  std::cout << linkedList.get(2) << std::endl;
  std::cout << linkedList.get(4) << std::endl;
  linkedList.addAtIndex(-1, 4);
  return 0;
}
